class Solution {
public:
    int mySqrt(int x) 
    {
        if(x <= 2 && x != 0)
            return 1;
        
        if(x == 0)
            return 0;

        long low = 2;
        long height = x / 2;

        while(low <= height)
        {
            long mid = (low + height) / 2;

            if(mid * mid == x)
                return mid;
            else if(mid * mid > x)
                height = mid - 1;
            else low = mid + 1;
        }

        return height;
    }
};

//二分查找法的边界确定很重要